package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname BubbleSort
 * @Project Data-structure-and-algorithm
 * @Description 冒泡排序代码实现优化版  【优化内容：如果发现在某糖排序中，相邻数字没有发生交换，可以提前结束冒泡排序】
 * 1、一共进行数组大小-1趟排序
 * 2、完成第一排序，就得到最大的一个数，放在最后面
 * 3、完成第二排序，就得到第二大的一个数，放在倒数第二个位置
 * 4、依次类推，直到数组只剩一个数时，排序完毕
 * @Author wpcheng
 * @Create 2021-08-01-9:47
 * @Version 1.0
 */
public class BubbleSortPlus {
    public static void main(String[] args) {
        int arr[] = {3,9,-1,10,20};

        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
//        int temp = 0;
//        boolean flag = false; //定义标志位，判断是否发生交换
//
//        for (int i = 0; i < arr.length-1; i++) { //O(n^2)
//            for (int j = 0; j < arr.length-1-i; j++) {
//                if (arr[j] > arr[j+1]) {//如果前面的数比后面的数大
//                    flag = true;
//                    temp = arr[j];
//                    arr[j] = arr[j+1];
//                    arr[j+1] = temp;
//                }
//            }
//            System.out.println("第"+(i+1)+"趟排序后的数组");
//            System.out.println(Arrays.toString(arr));
//
//            if (!flag){ //没有发生交换
//                break;
//            }else {
//                flag = false; //发生交换,把flag重新置为false，给下次排序使用
//            }
//
//        }
    }

    /**
     * 把上面的排序算法注释掉，封装成一个方法
     * @param arr 要排序的数组
     */
    public static void bubbleSort(int[] arr){
        int temp = 0;
        boolean flag = false; //定义标志位，判断是否发生交换

        for (int i = 0; i < arr.length-1; i++) { //O(n^2)
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {//如果前面的数比后面的数大
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
//            System.out.println("第"+(i+1)+"趟排序后的数组");
//            System.out.println(Arrays.toString(arr));
            if (!flag){ //没有发生交换
                break;
            }else {
                flag = false; //发生交换,把flag重新置为false，给下次排序使用
            }
        }
    }



}
